{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make String a Subsequence Using Cyclic Increments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canMakeSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #循环增长使字符串子序列等于另一个字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>str1</code> 和&nbsp;<code>str2</code>&nbsp;。</p>\n",
    "\n",
    "<p>一次操作中，你选择&nbsp;<code>str1</code>&nbsp;中的若干下标。对于选中的每一个下标&nbsp;<code>i</code>&nbsp;，你将&nbsp;<code>str1[i]</code>&nbsp;<strong>循环</strong>&nbsp;递增，变成下一个字符。也就是说&nbsp;<code>'a'</code>&nbsp;变成&nbsp;<code>'b'</code>&nbsp;，<code>'b'</code> 变成&nbsp;<code>'c'</code>&nbsp;，以此类推，<code>'z'</code> 变成&nbsp;<code>'a'</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果执行以上操作 <strong>至多一次</strong>&nbsp;，可以让 <code>str2</code>&nbsp;成为 <code>str1</code>&nbsp;的子序列，请你返回 <code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p><b>注意：</b>一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>str1 = \"abc\", str2 = \"ad\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>选择 str1 中的下标 2 。\n",
    "将 str1[2] 循环递增，得到 'd' 。\n",
    "因此，str1 变成 \"abd\" 且 str2 现在是一个子序列。所以返回 true 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>str1 = \"zc\", str2 = \"ad\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>选择 str1 中的下标 0 和 1 。\n",
    "将 str1[0] 循环递增得到 'a' 。\n",
    "将 str1[1] 循环递增得到 'd' 。\n",
    "因此，str1 变成 \"ad\" 且 str2 现在是一个子序列。所以返回 true 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>str1 = \"ab\", str2 = \"d\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>这个例子中，没法在执行一次操作的前提下，将 str2 变为 str1 的子序列。\n",
    "所以返回 false 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= str1.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= str2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>str1</code>&nbsp;和&nbsp;<code>str2</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-string-a-subsequence-using-cyclic-increments](https://leetcode.cn/problems/make-string-a-subsequence-using-cyclic-increments/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-string-a-subsequence-using-cyclic-increments](https://leetcode.cn/problems/make-string-a-subsequence-using-cyclic-increments/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"ad\"', '\"zc\"\\n\"ad\"', '\"ab\"\\n\"d\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        \n",
    "        def helper(x):\n",
    "            return chr(ord('a') + (ord(x)-ord('a')+1) % 26)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            \n",
    "            if j == len(str2):\n",
    "                return True\n",
    "            if i == len(str1):\n",
    "                return False\n",
    "            \n",
    "            if str1[i] == str2[j] or helper(str1[i]) == str2[j]:\n",
    "                return dp(i+1, j+1)\n",
    "            # elif helper(str1[i]) == str2[j]:\n",
    "            #     return dp(i+1, j+1) or dp(i+1, j)\n",
    "            return dp(i+1, j)\n",
    "                \n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "\n",
    "        n1,n2 = len(str1),len(str2)\n",
    "        idx = 0\n",
    "\n",
    "        for i in range(n1):\n",
    "            if str1[i]==str2[idx] or ((ord(str1[i])-ord('a')+1)%26 == (ord(str2[idx])-ord('a'))):\n",
    "                idx+=1\n",
    "            if idx>=n2:\n",
    "                break\n",
    "        \n",
    "        return idx>=n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, s: str, t: str) -> bool:\n",
    "        if len(s) < len(t):\n",
    "            return False\n",
    "        j = 0\n",
    "        for b in s:\n",
    "            c = chr(ord(b) + 1) if b != 'z' else 'a'\n",
    "            if b == t[j] or c == t[j]:\n",
    "                j += 1\n",
    "                if j == len(t):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        res = False\n",
    "        n = len(str1)\n",
    "        m = len(str2)\n",
    "        if m > n:\n",
    "            return False\n",
    "        index = 0\n",
    "        \n",
    "        for _char in str2:\n",
    "            bfind = False\n",
    "            while index < n:\n",
    "                _char_1 = str1[index]\n",
    "                _char_2 = chr(ord(_char_1) + 1) if _char_1 != 'z'  else 'a'\n",
    "                #print(_char, _char_1, _char_2)\n",
    "                if _char_1 == _char or _char_2 == _char:\n",
    "                    bfind = True\n",
    "                    index += 1\n",
    "                    break\n",
    "                index += 1\n",
    "            if not bfind:\n",
    "                return False\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        str1 = str1[::-1]\n",
    "        str2 = str2[::-1]\n",
    "        l1 = l2 = 0\n",
    "        print(str1, str2)\n",
    "        while l1 < len(str1) and l2 < len(str2):\n",
    "            if ord(str2[l2]) - ord(str1[l1]) in [0, 1, -25]:\n",
    "                l1 += 1\n",
    "                l2 += 1\n",
    "            else:\n",
    "                l1 += 1\n",
    "        if l2 == len(str2): return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        k = len(str2)\n",
    "        n = len(str1)\n",
    "\n",
    "        # for i in range(n-k+1):\n",
    "        #     flag = True\n",
    "        #     for j in range(k):\n",
    "        #         ls = [str1[i+j]]\n",
    "        #         asc = (ord(str1[i+j])+1-ord('a'))%26 + ord('a')\n",
    "        #         c = chr(asc)\n",
    "        #         ls.append(c)\n",
    "        #         if str2[j] not in ls: \n",
    "        #             flag = False\n",
    "        #             break\n",
    "        #     if flag: return True\n",
    "        de = deque(str2)\n",
    "        i = 0\n",
    "        while de and i < n:\n",
    "            ls = [str1[i]]\n",
    "            asc = (ord(str1[i])+1-ord('a'))%26 + ord('a')\n",
    "            c = chr(asc)\n",
    "            ls.append(c)\n",
    "\n",
    "            if de[0] in ls:\n",
    "                de.popleft()\n",
    "\n",
    "            i+=1\n",
    "\n",
    "        return False if de else True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        s2 = [chr((ord(c) - ord('a') + 1) % 26 + ord('a')) for c in str1]\n",
    "        n1 = len(str1)\n",
    "        n2 = len(str2)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n1 and j < n2:\n",
    "            if str1[i] == str2[j] or s2[i] == str2[j]:\n",
    "                j += 1\n",
    "            i += 1\n",
    "        if j == n2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        if len(str1) < len(str2):\n",
    "            return False\n",
    "        str2Pre = \"\".join(['z' if ch == 'a' else chr(ord(ch) - 1) for ch in str2])\n",
    "        idx = 0\n",
    "        for ch in str1:\n",
    "            if ch == str2[idx] or ch == str2Pre[idx]:\n",
    "                idx += 1\n",
    "                if idx == len(str2):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        str1 = [ord(i) - 97 for i in str1]\n",
    "        str2 = [ord(i) - 97 for i in str2]\n",
    "        p = 0\n",
    "        for i in str1:\n",
    "            if (str2[p] - i) % 26 <= 1:\n",
    "                p += 1\n",
    "            if p == len(str2):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        list_1 = list(str1)\n",
    "        list_2 = list(str2)\n",
    "\n",
    "        j=0\n",
    "        \n",
    "        res = False\n",
    "\n",
    "        for ele in list_1:\n",
    "            ele_ord = ord(ele)\n",
    "            ele_ord_next = ord(ele)+1 if ele != 'z' else ord('a')\n",
    "            \n",
    "            \n",
    "            if ele_ord == ord(list_2[j]): j+=1\n",
    "            elif ele_ord_next == ord(list_2[j]):j+=1\n",
    "\n",
    "\n",
    "            if j == len(list_2): return True\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        po, pt = 0, 0\n",
    "        str1, str2 = list(str1), list(str2)\n",
    "        while po < len(str1):\n",
    "            if str1[po] == str2[pt]:\n",
    "                pt += 1\n",
    "            else:\n",
    "                if str1[po] == 'z':\n",
    "                    if str2[pt] == 'a':\n",
    "                        pt += 1\n",
    "                else:\n",
    "                    if ord(str1[po]) + 1 == ord(str2[pt]):\n",
    "                        pt += 1\n",
    "\n",
    "            if pt >= len(str2):\n",
    "                return True\n",
    "            po += 1\n",
    "\n",
    "        \n",
    "        return pt >= len(str2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        str1, str2 = list(str1), deque(list(str2))\n",
    "        for ch in str1:\n",
    "            if not str2:\n",
    "                return True\n",
    "            if str2[0] == ch or ord(str2[0])-ord(ch) in {1, -25}:\n",
    "                str2.popleft()\n",
    "        \n",
    "        return True if not str2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMakeSubsequence(self, str1: str, str2: str) -> bool:\n",
    "        def change(ch):\n",
    "            return {ch, chr((ord(ch) - ord('a') + 1) % 26 + ord('a'))}\n",
    "        l = list(str1)[::-1]\n",
    "        for ch in str2:\n",
    "            check = False\n",
    "            while len(l) > 0:\n",
    "                d = change(l.pop())\n",
    "                # print(d, l)\n",
    "                if ch in d:\n",
    "                    check = True\n",
    "                    break\n",
    "            if not check:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
